package org.chnxi.study.leetcode.questions25.ques23;

/**
 * 合并K个排序链表
 * 执行用时 :423 ms, 在所有 Java 提交中击败了5.02%的用户
 * 内存消耗 :41.4 MB, 在所有 Java 提交中击败了60.29%的用户
 */
public class Simple01 {

    public static void main(String[] args) {
        ListNode l1_1 = new ListNode(1);
        ListNode l1_2 = new ListNode(4);
        ListNode l1_3 = new ListNode(5);
        l1_1.next = l1_2;
        l1_2.next = l1_3;

        ListNode l2_1 = new ListNode(1);
        ListNode l2_2 = new ListNode(3);
        ListNode l2_3 = new ListNode(4);
        l2_1.next = l2_2;
        l2_2.next = l2_3;

        ListNode l3_1 = new ListNode(2);
        ListNode l3_2 = new ListNode(6);
        l3_1.next = l3_2;

        ListNode[] lists = new ListNode[]{l1_1, l2_1, l3_1};

        ListNode result = mergeKLists(lists);
        System.out.println(result);

    }

    public static ListNode mergeKLists(ListNode[] lists) {
        ListNode result = new ListNode(0);
        ListNode curNode = result;

        int[] nums = new int[lists.length];
        int nullCount = 0;
        do{
            nullCount = 0;
            for (int i=0; i<lists.length; i++){
                if(lists[i] == null){
                    nullCount++;
                    nums[i] = Integer.MAX_VALUE;
                }else{
                    nums[i] = lists[i].val;
                }
            }

            if(nullCount >= lists.length){
                break;
            }

            int idx = getMinValIdx(nums);

            ListNode tmp = new ListNode(lists[idx].val);
            curNode.next = tmp;
            curNode = tmp;

            lists[idx] = lists[idx] == null ? null : lists[idx].next;

        }while (true);

        return result.next;
    }

    private static int getMinValIdx(int[] nums){
        int minNum = Integer.MAX_VALUE;
        int minNumIdx = -1;
        for (int i=0; i<nums.length; i++){
            if(nums[i] < minNum){
                minNum = nums[i];
                minNumIdx = i;
            }
        }
        return minNumIdx;
    }

}
